{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Blending Problem\n", "## Problem definition" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Kahuna company manufactures sausages using three kinds of meat. The relevant information about the ingredients is provided in the table below:\n", "\n", "| Ingredient | Cost (€/kg) | Availability (kg) |\n", "|------------|--------------|-------------------|\n", "| Pork | 4.32 | 30 |\n", "| Wheat | 2.46 | 20 |\n", "| Starch | 1.86 | 17 |\n", "\n", "The company makes two types of sausages:\n", "* Economy (>=40% Pork)\n", "* Premium (>=60% Pork)\n", "\n", "One sausage is 50 grams (0.05 kg)\n", "\n", "According to government regulations, the most starch we can use in our sausages is 25%\n", "\n", "We have a contract with a butcher, and have already purchased 23 kg pork, that will go bad if it's not used.\n", "\n", "We have a demand for 350 economy sausages and 500 premium sausages.\n", "\n", "**Write a linear program to figure out how to most cost effectively blend our sausages.**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's model our problem\n", "\n", " *pe* = Pork in the economy sausages (kg) \n", " *we* = Wheat in the economy sausages (kg) \n", " *se* = Starch in the economy sausages (kg) \n", " *pp* = Pork in the premium sausages (kg) \n", " *wp* = Wheat in the premium sausages (kg) \n", " *sp* = Starch in the premium sausages (kg) \n", "\n", "We want to minimise costs such that:\n", "\n", "Cost = 4.32(*pe* + *pp*) + 2.46(*we* + *wp*) + 1.86(*se* + *sp*)\n", "\n", "\n", "With the following constraints:\n", "\n", " *pe* + *we* + *se* = 350 \\* 0.05 \n", " *pp* + *wp* + *sp* = 500 \\* 0.05 \n", " *pe* ≥ 0.4(*pe* + *we* + *se*) \n", " *pp* ≥ 0.6(*pp* + *wp* + *sp*) \n", " *se* ≤ 0.25(*pe* + *we* + *se*) \n", " *sp* ≤ 0.25(*pp* + *wp* + *sp*) \n", " *pe* + *pp* ≤ 30 \n", " *we* + *wp* ≤ 20 \n", " *se* + *sp* ≤ 17 \n", " *pe* + *pp* ≥ 23" ] }, { "cell_type": "code", "execution_count": null, "outputs": [], "source": [ "!pip install pandas\n", "!pip install numpy\n", "!pip install pulp" ], "metadata": { "collapsed": false, "pycharm": { "name": "#%%\n" } } }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import pandas as pd\n", "import numpy as np\n", "from IPython.display import display, Markdown\n", "import pulp" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Instantiate our problem class\n", "model = pulp.LpProblem(\"Cost minimising blending problem\", pulp.LpMinimize)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here we have 6 decision variables, we could name them individually but this wouldn't scale up if we had hundreds/thousands of variables (you don't want to be entering all of these by hand multiple times). \n", "\n", "We'll create a couple of lists from which we can create tuple indices." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# Construct our decision variable lists\n", "sausage_types = ['economy', 'premium']\n", "ingredients = ['pork', 'wheat', 'starch']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each of these decision variables will have similar characteristics (lower bound of 0, continuous variables). Therefore we can use PuLP's LpVariable object's dict functionality, we can provide our tuple indices.\n", "\n", "These tuples will be keys for the ing_weight dict of decision variables" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "variables = pulp.LpVariable.dicts(\"weight kg\",\n", " ((i, j) for i in sausage_types for j in ingredients),\n", " lowBound=0,\n", " cat='Continuous')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "PuLP provides an lpSum vector calculation for the sum of a list of linear expressions.\n", "\n", "Whilst we only have 6 decision variables, I will demonstrate how the problem would be constructed in a way that could be scaled up to many variables using list comprehensions." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "#coefficients\n", "coefficients = [4.32, 2.46, 1.86]\n", "\n", "# Objective Function\n", "model += (\n", " pulp.lpSum([\n", " coefficients[j] * variables[(i, ingredients[j])]\n", " for i in sausage_types for j in range(len(ingredients))])\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we add our constraints, bear in mind again here how the use of list comprehensions allows for scaling up to many ingredients or sausage types" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "# Constraints\n", "# 350 economy and 500 premium sausages at 0.05 kg\n", "model += pulp.lpSum([variables['economy', j] for j in ingredients]) == 350 * 0.05, \"Economy demand\"\n", "model += pulp.lpSum([variables['premium', j] for j in ingredients]) == 500 * 0.05, \"Premium demand\"\n", "\n", "# Economy has >= 40% pork, premium >= 60% pork\n", "model += variables['economy', 'pork'] >= (\n", " 0.4 * pulp.lpSum([variables['economy', j] for j in ingredients])), \"40% Pork in Economy\"\n", "\n", "model += variables['premium', 'pork'] >= (\n", " 0.6 * pulp.lpSum([variables['premium', j] for j in ingredients])), \"60$ Pork in Premium\"\n", "\n", "# Sausages must be <= 25% starch\n", "model += variables['economy', 'starch'] <= (\n", " 0.25 * pulp.lpSum([variables['economy', j] for j in ingredients])), \"25% Starch in Economy\"\n", "\n", "model += variables['premium', 'starch'] <= (\n", " 0.25 * pulp.lpSum([variables['premium', j] for j in ingredients])), \"25% Starch in Premium\"\n", "\n", "# We have at most 30 kg of pork, 20 kg of wheat and 17 kg of starch available\n", "model += pulp.lpSum([variables[i, 'pork'] for i in sausage_types]) <= 30, \"Pork Availability\"\n", "model += pulp.lpSum([variables[i, 'wheat'] for i in sausage_types]) <= 20, \"Wheat Availability\"\n", "model += pulp.lpSum([variables[i, 'starch'] for i in sausage_types]) <= 17, \"Starch Availability\"\n", "\n", "# We have at least 23 kg of pork to use up\n", "model += pulp.lpSum([variables[i, 'pork'] for i in sausage_types]) >= 23, \"Pork Stock\"" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Academic license - for non-commercial use only\n" ] }, { "data": { "text/plain": [ "'Optimal'" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Solve our problem\n", "model.solve(solver=pulp.solvers.GUROBI(msg = 0))\n", "pulp.LpStatus[model.status]" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/markdown": [ "Total cost is 140.96 €" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/markdown": [ "The following table shows the decision variables: " ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
VariablesSolution (GRB)Reduced cost (GRB)Objective Coefficient (GRB)Objective Lower bound (GRB)Objective Upper bound (GRB)
(economy, pork)weight_kg_('economy',_'pork')7.000.004.324.32Inf
(economy, wheat)weight_kg_('economy',_'wheat')6.120.002.461.862.46
(economy, starch)weight_kg_('economy',_'starch')4.380.001.86-Inf2.46
(premium, pork)weight_kg_('premium',_'pork')16.000.004.322.464.32
(premium, wheat)weight_kg_('premium',_'wheat')2.750.002.462.464.32
(premium, starch)weight_kg_('premium',_'starch')6.250.001.86-Inf2.46
\n", "
" ], "text/plain": [ " Variables Solution (GRB) \\\n", "(economy, pork) weight_kg_('economy',_'pork') 7.00 \n", "(economy, wheat) weight_kg_('economy',_'wheat') 6.12 \n", "(economy, starch) weight_kg_('economy',_'starch') 4.38 \n", "(premium, pork) weight_kg_('premium',_'pork') 16.00 \n", "(premium, wheat) weight_kg_('premium',_'wheat') 2.75 \n", "(premium, starch) weight_kg_('premium',_'starch') 6.25 \n", "\n", " Reduced cost (GRB) Objective Coefficient (GRB) \\\n", "(economy, pork) 0.00 4.32 \n", "(economy, wheat) 0.00 2.46 \n", "(economy, starch) 0.00 1.86 \n", "(premium, pork) 0.00 4.32 \n", "(premium, wheat) 0.00 2.46 \n", "(premium, starch) 0.00 1.86 \n", "\n", " Objective Lower bound (GRB) Objective Upper bound (GRB) \n", "(economy, pork) 4.32 Inf \n", "(economy, wheat) 1.86 2.46 \n", "(economy, starch) -Inf 2.46 \n", "(premium, pork) 2.46 4.32 \n", "(premium, wheat) 2.46 4.32 \n", "(premium, starch) -Inf 2.46 " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/markdown": [ "The following table shows the constraints: " ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ConstraintRight Hand SideSlackShadow PriceMin RHSMax RHS
0Economy_demand17.500.002.3110.6220.00
1Premium_demand25.000.002.3121.3326.67
240%_Pork_in_Economy0.000.000.00-2.751.00
360$_Pork_in_Premium0.00-1.000.00-Inf1.00
425%_Starch_in_Economy0.000.00-0.60-4.386.12
525%_Starch_in_Premium0.000.00-0.60-6.252.75
6Pork_Availability30.007.000.0023.00Inf
7Wheat_Availability20.0011.120.008.88Inf
8Starch_Availability17.006.380.0010.62Inf
9Pork_Stock23.000.001.8622.0025.75
\n", "
" ], "text/plain": [ " Constraint Right Hand Side Slack Shadow Price Min RHS Max RHS\n", "0 Economy_demand 17.50 0.00 2.31 10.62 20.00\n", "1 Premium_demand 25.00 0.00 2.31 21.33 26.67\n", "2 40%_Pork_in_Economy 0.00 0.00 0.00 -2.75 1.00\n", "3 60$_Pork_in_Premium 0.00 -1.00 0.00 -Inf 1.00\n", "4 25%_Starch_in_Economy 0.00 0.00 -0.60 -4.38 6.12\n", "5 25%_Starch_in_Premium 0.00 0.00 -0.60 -6.25 2.75\n", "6 Pork_Availability 30.00 7.00 0.00 23.00 Inf\n", "7 Wheat_Availability 20.00 11.12 0.00 8.88 Inf\n", "8 Starch_Availability 17.00 6.38 0.00 10.62 Inf\n", "9 Pork_Stock 23.00 0.00 1.86 22.00 25.75" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "total_cost = pulp.value(model.objective)\n", "display(Markdown(\"Total cost is %0.2f €\"%total_cost))\n", "\n", "display(Markdown(\"The following table shows the decision variables: \"))\n", "var_df = pd.DataFrame.from_dict(variables, orient=\"index\", \n", " columns = [\"Variables\"])\n", "var_df[\"Solution (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.X))\n", "var_df[\"Reduced cost (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.RC))\n", "var_df[\"Objective Coefficient (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.Obj))\n", "var_df[\"Objective Lower bound (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.SAObjLow) if item.solverVar.SAObjLow > -0.1 else \"-Inf\" )\n", "var_df[\"Objective Upper bound (GRB)\"] = var_df[\"Variables\"].apply(lambda item: \"{:.2f}\".format(item.solverVar.SAObjUp) if item.solverVar.SAObjUp != item.solverVar.UB else \"Inf\")\n", "\n", "\n", "display(var_df)\n", "\n", "\n", "const_dict = dict(model.constraints)\n", "con_df = pd.DataFrame.from_records(list(const_dict.items()), exclude=[\"Expression\"], columns=[\"Constraint\", \"Expression\"])\n", "con_df[\"Right Hand Side\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.RHS))\n", "con_df[\"Slack\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.Slack))\n", "con_df[\"Shadow Price\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.Pi))\n", "con_df[\"Min RHS\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.SARHSLow) if const_dict[item].solverConstraint.SARHSLow > -1e10 else \"-Inf\")\n", "con_df[\"Max RHS\"]=con_df[\"Constraint\"].apply(lambda item: \"{:.2f}\".format(const_dict[item].solverConstraint.SARHSUp) if const_dict[item].solverConstraint.SARHSUp < 1e10 else \"Inf\" )\n", "\n", "\n", "display(Markdown(\"The following table shows the constraints: \"))\n", "display(con_df)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 1 }